#include <iostream>
#include <ctime>
#include <vector>

using namespace std;
int num = 0;

// 动态规划  自下向上
int fib(int n){
	vector<int> memo(n+1, -1);		// 存储n+1个元素 0-n
	
	memo[0] = 0;
	memo[1] = 1;
	for(int i = 2; i <= n; i++)
		memo[i] = memo[i - 1] + memo[i - 2];
	return memo[n];
}


int main(){
	num = 0;
	int n = 1000;
	time_t startTime = clock();
	int res = fib(n);
	time_t endTime = clock();
	
	cout << "fib(" << n << ") = " << res << endl;
    cout << "time : " << double(endTime - startTime) / CLOCKS_PER_SEC << " s" << endl;
    cout << "run function fib() " << num << " times." << endl;
}
